﻿namespace Leetcode.N0018;
public class Solution
{
    public IList<IList<int>> FourSum(int[] nums, int target)
    {
        nums = nums.OrderBy(i => i).ToArray();

        var ans = new List<IList<int>>();
        for (int n1 = 0; n1 <= nums.Length - 4; n1++)
        {
            if (n1 > 0 && nums[n1] == nums[n1 - 1])
            {
                continue;
            }

            if ((long)nums[n1] + nums[n1 + 1] + nums[n1 + 2] + nums[n1 + 3] > target)
            {
                break;
            }

            if ((long)nums[n1] + nums[nums.Length - 1] + nums[nums.Length - 2] + nums[nums.Length - 3] < target)
            {
                continue;
            }

            for (int n2 = n1 + 1; n2 <= nums.Length - 3; n2++)
            {
                if (n2 > n1 + 1 && nums[n2] == nums[n2 - 1])
                {
                    continue;
                }

                if ((long)nums[n1] + nums[n2] + nums[n2 + 1] + nums[n2 + 2] > target)
                {
                    break;
                }

                if ((long)nums[n1] + nums[n2] + nums[nums.Length - 1] + nums[nums.Length - 2] < target)
                {
                    continue;
                }

                var n3 = n2 + 1;
                var n4 = nums.Length - 1;
                while (n3 < n4)
                {
                    long val = (long)nums[n1] + nums[n2] + nums[n3] + nums[n4];
                    if (val == target)
                    {
                        ans.Add(new List<int> { nums[n1], nums[n2], nums[n3], nums[n4] });
                        while (n4 - n3 > 1 && nums[n3] == nums[n3 + 1])
                        {
                            n3++;
                        }
                        n3++;

                        while (n4 - n3 > 1 && nums[n4] == nums[n4 - 1])
                        {
                            n4--;
                        }
                        n4--;
                    }
                    else if (val < target)
                    {
                        n3++;
                    }
                    else
                    {
                        n4--;
                    }

                }

            }

        }

        return ans;
    }
}
